//二叉树的基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node 
{	
	ElemType data;			//数据元素
	struct node *lchild;	//指向左孩子节点
	struct node *rchild;	//指向右孩子节点
} BTNode;

void DestroyBTree(BTNode *&b)
{	if (b!=NULL)
{	DestroyBTree(b->lchild);
	DestroyBTree(b->rchild);
	free(b);
}
}

void DispBTree(BTNode *b) 
{
	if (b!=NULL)
	{	printf("%c",b->data);
		if (b->lchild!=NULL || b->rchild!=NULL)
		{	printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild!=NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}


BTNode *CreateBT2(char *post /*指向后序序列开头的指针*/, char *in /*指向中序序列开头的指针*/, int n)
{
	
	char r9b3 = '0';
	char *p9t3 = NULL;
	int i;
	if (n <= 0 || post == nullptr || in == nullptr) 
		return nullptr;
	
	r9b3 = *(post + n - 1);//树根
	BTNode *b9V3 = (BTNode *)malloc(sizeof(node));
	b9V3->data = r9b3; //我们要创建的树根节点建立好了
	
	for (p9t3 = in; p9t3 < in + n; ++p9t3)//p走到中序序列的根结点处
		if (*p9t3 == r9b3)
			break;
	
	i = p9t3 - in; //k是左子树节点数
	
	b9V3->lchild = CreateBT2(post, in, i); //这两个语句最关键
	b9V3->rchild = CreateBT2(post + i, p9t3 + 1, n - i - 1);
	
	return b9V3;
}


void PreOrder(BTNode *b)  		//先序遍历的递归算法
{
	if (b!=NULL)  
	{
		printf("%c ",b->data);	//访问根结点
		PreOrder(b->lchild);	//先序遍历左子树
		PreOrder(b->rchild);	//先序遍历右子树
	}
}

int main()
{

	char s9t3r1[MaxSize] = {0};
	char s9t3r2[MaxSize] = {0};
	printf("输入后序序列：");
	scanf("%s",s9t3r1);
	int len1 = 0;
	while(s9t3r1[len1]!='\0')len1++;
	
	
	printf("输入中序序列：");
	scanf("%s",s9t3r2);
	int len2 = 0;
	while(s9t3r2[len2]!='\0')len2++;
	
	
	if(len1!=len2)
		printf("输入不合法！\n");
	
	BTNode*root = CreateBT2(s9t3r1,s9t3r2,len1);
	
	printf("先序序列为：");
	PreOrder(root);

	return 0;
}

